# 从中序与后序遍历序列构造二叉树
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def buildTree(self, inorder, postorder) -> TreeNode:
        if len(postorder) == 0 or len(inorder) == 0:
            return None
        root = TreeNode(postorder[-1])
        root_index = inorder.index(postorder[-1])
        left = self.buildTree(inorder[:root_index], postorder[:root_index], )
        right = self.buildTree(inorder[root_index + 1:], postorder[root_index:-1])
        root.left = left
        root.right = right
        return root


if __name__ == '__main__':
    so = Solution()
    inorder = [9, 3, 15, 20, 7]
    postorder = [9, 15, 7, 20, 3]
    r = so.buildTree( inorder, postorder)
    print(r)
